home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Enigma Amiga Life 109
/
EnigmaAmiga109CD.iso
/
dalla rivista
/
host contacted
/
jikes.lha
/
jikes-1.11
/
src
/
jcl
/
jcl_dynamic.h
< prev
next >
Wrap
C/C++ Source or Header
|
1999-12-09
|
8KB
|
254 lines
// $Id: jcl_dynamic.h,v 1.2 1999/12/09 18:02:26 lord Exp $
//
// This software is subject to the terms of the IBM Jikes Compiler
// License Agreement available at the following URL:
// http://www.ibm.com/research/jikes.
// Copyright (C) 1996, 1998, International Business Machines Corporation
// and others. All Rights Reserved.
// You must accept the terms of that agreement to use this software.
//
#ifndef jcl_DYNAMIC_INCLUDED
#define jcl_DYNAMIC_INCLUDED
#include <stdlib.h>
#include <string.h>
//
// This DynamicArray template class can be used to construct a dynamic
// array of arbitrary objects. The space for the array is allocated in
// blocks of size 2**LOG_BLKSIZE. In declaring a dynamic array the user
// may specify a value for LOG_BLKSIZE which by default is 10. Also,
// as the array is implemented using a base+offset strategy, the user
// may also specify the number of "slots" to add to the base when the
// current base runs out of space. Each slot points to a block.
//
template <class T, int LOG_BLKSIZE = 10, int BASE_INCREMENT = 16>
class DynamicArray
{
T **base;
int base_size,
top,
size;
//
// Reallocate the base and initialize the new elements to NULL.
//
void reallocate_base();
//
// Allocate another block of storage for the dynamic array.
//
void allocate_more_space();
public:
//
// This function is invoked with an integer argument n. It ensures
// that enough space is allocated for n elements in the dynamic array.
// I.e., that the array will be indexable in the range (0..n-1)
//
// Note that this function can be used as a garbage collector. When
// invoked with no argument(or 0), it frees up all dynamic space that
// was allocated for the array.
//
void resize(const int n = 0);
//
// This function is used to reset the size of a dynamic array without
// allocating or deallocting space. It may be invoked with an integer
// argument n which indicates the new size or with no argument which
// indicates that the size should be reset to 0.
//
void reset(const int n = 0)
{
if (n < 0 || n >= size)
/* throw range exception */ ;
top = n;
}
//
// Return length of the dynamic array.
//
int length() { return top; }
//
// Return a reference to the ith element of the dynamic array.
//
// Note that no check is made here to ensure that 0 <= i < top.
// Such a check might be useful for debugging and a range exception
// should be thrown if it yields true.
//
T& operator[](const int i) { return base[i >> LOG_BLKSIZE][i]; }
//
// Add an element to the dynamic array and return the top index.
//
int next_index()
{
int i = top++;
if (i == size)
allocate_more_space();
return i;
}
//
// Add an element to the dynamic array and return a reference to
// that new element.
//
T& next() { int i = next_index(); return base[i >> LOG_BLKSIZE][i]; }
//
// Assignment of a dynamic array to another.
//
DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>&
operator=(const DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>& rhs)
{
if (this != &rhs)
{
resize(rhs.top);
for (int i = 0; i < rhs.top; i++)
base[i >> LOG_BLKSIZE][i] = rhs.base[i >> LOG_BLKSIZE][i];
}
return *this;
}
//
// Constructor of a dynamic array.
//
DynamicArray(const int n = 0)
{
base_size = 0;
size = 0;
base = NULL;
resize(n);
}
//
// Initialization of a dynamic array.
//
DynamicArray(const DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>& rhs)
{
base_size = 0;
size = 0;
base = NULL;
*this = rhs;
}
//
// Destructor of a dynamic array.
//
~DynamicArray() { resize(0); }
};
//
// Reallocate the base and initialize the new elements to null.
//
template <class T, int LOG_BLKSIZE, int BASE_INCREMENT>
void DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>::reallocate_base()
{
int old_base_size = base_size;
T **old_base = base;
base_size += BASE_INCREMENT;
base = new T*[base_size];
if (old_base != NULL)
memmove(base, old_base, old_base_size * sizeof(T *));
memset(&base[old_base_size], 0, (base_size - old_base_size) * sizeof(T *));
}
//
// Allocate another block of storage for the dynamic array.
//
template <class T, int LOG_BLKSIZE, int BASE_INCREMENT>
void DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>::allocate_more_space()
{
//
// The variable size always indicates the maximum number of
// elements that has been allocated for the array.
// Initially, it is set to 0 to indicate that the array is empty.
// The pool of available elements is divided into segments of size
// 2**log_blksize each. Each segment is pointed to by a slot in
// the array base.
//
// By dividing size by the size of the segment we obtain the
// index for the next segment in base. If base is full, it is
// reallocated.
//
//
int blksize = 1 << LOG_BLKSIZE;
int k = size >> LOG_BLKSIZE; /* which segment? */
if (k == base_size) // base overflowed? reallocate
reallocate_base();
//
// We allocate a new segment and place its adjusted address in
// base[k]. The adjustment allows us to index the segment directly,
// instead of having to perform a subtraction for each reference.
// See operator[] below.
//
base[k] = new T[blksize];
base[k] -= size;
//
// Finally, we update SIZE.
//
size += blksize;
return;
}
//
// This function is invoked with an integer argument n. It ensures
// that enough space is allocated for n elements in the dynamic array.
// I.e., that the array will be indexable in the range (0..n-1)
//
// Note that this function can be used as a garbage collector. When
// invoked with no argument(or 0), it frees up all dynamic space that
// was allocated for the array.
//
template <class T, int LOG_BLKSIZE, int BASE_INCREMENT>
void DynamicArray<T, LOG_BLKSIZE, BASE_INCREMENT>::resize(const int n)
{
//
// If array did not previously contain enough space, allocate
// the necessary additional space. Otherwise, if the array had
// more blocks than are needed, release the extra blocks.
//
if (n > size)
{
do
{
allocate_more_space();
} while (n > size);
}
else if (n < size)
{
// slot is the index of the base element whose block
// will contain the (n-1)th element.
int blksize = 1 << LOG_BLKSIZE;
int slot = (n <= 0 ? -1 : (n - 1) >> LOG_BLKSIZE);
for (int k = (size >> LOG_BLKSIZE) - 1; k > slot; k--)
{
size -= blksize;
base[k] += size;
delete [] base[k];
base[k] = NULL;
}
if (slot < 0)
{
delete [] base;
base = NULL;
base_size = 0;
}
}
top = n;
}
#endif /* #ifndef DYNAMIC_INCLUDED */